﻿/**
 * <vendor>
 *  Copyright 2010 Quanben Tech.
 * </vendor>
 * 
 * <summary>
 *  An implementation of B-tree
 * </summary>
 */

using System;
using System.Text;
using System.Collections.Generic;


namespace QSharp.Scheme.Classical.Trees
{
    using Sequential;

    public static class BTree
    {
        public interface INode<NodeType, T> 
            where NodeType : INode<NodeType, T>
        {
            NodeType GetChild(int index);
            void SetChild(int index, NodeType node);
            void AppendChild(NodeType node);
            void InsertChild(int index, NodeType node);
            void RemoveChild(int index);

            T GetEntry(int index);
            void SetEntry(int index, T entry);
            void AppendEntry(T entry);
            void InsertEntry(int index, T entry);
            void RemoveEntry(int index);

            /**
             * <remarks>
             *  to remove entries from `start'-th and all relevant child nodes
             *  (after that `start' entries and `start+1' nodes remain
             * </remarks>
             */
            void RemoveFrom(int start);

            NodeType Parent { get; set; }

            int EntryCount { get; }
            int ChildCount { get; }

            bool IsLeaf();
        }

        public interface INodeCreator<NodeType, T>
            where NodeType : INode<NodeType, T>
        {
            NodeType Create();
        }

        public static int MaximalEntryCount(int order)
        {
            return order - 1;
        }

        public static int MinimalEntryCount(int order)
        {
            return (order + 1) / 2 - 1;
        }

        public static int MaximalChildCount(int order)
        {
            return order;
        }

        public static int MinimalChildCount(int order)
        {
            return (order + 1) / 2;
        }

        public static void SearchForChild_Linear<NodeType, T>(NodeType parent, NodeType child, out int index)
            where NodeType : INode<NodeType, T>
        {
            NodeType p;
            int c = parent.ChildCount;
            for (index = 0; index < c; index++)
            {
                p = parent.GetChild(index);
                if ((object)p == (object)child)
                    return;
            }
            return;
        }

        public static void SearchForChild_Binary<NodeType, T>(NodeType parent, NodeType child, out int index)
            where NodeType : INode<NodeType, T>
            where T : IComparable<T>
        {
            NodeType p;
            int c = parent.ChildCount;
            if (child.EntryCount == 0)
            {
                for (index = 0; index < c; index++)
                {
                    p = parent.GetChild(index);
                    if ((object)p == (object)child)
                        return;
                }
                return;
            }

            T t = child.GetEntry(0);

            int i;
            SearchOnNode_Binary<NodeType, T>(parent, t, out i);

            p = parent.GetChild(i);
            if ((object)p == (object)child)
            {
                index = i;
                return;
            }

            int ce = parent.EntryCount;
            for (index = i - 1; index >= 0; index--)
            {
                if (t.CompareTo(parent.GetEntry(index)) > 0)
                    break;
                p = parent.GetChild(index);
                if ((object)p == (object)child)
                    return;
            }
            
            for (index = i + 1; index < ce; index++)
            {
                if (t.CompareTo(parent.GetEntry(index)) < 0)
                    break;
                p = parent.GetChild(index);
                if ((object)p == (object)child)
                    return;
            }

            // the last candidate which may possibly be the target
            p = parent.GetChild(index);
        }


        /**
         * <summary>
         *  Linear search
         *  
         *  Search the position of an entry with specified value `t' on `node' 
         *  if not found, the method gives the index where a new entry is
         *  supposed to be inserted (bigger entry)
         *  
         *  a node is not allowed to be with 0 entries
         *  
         * </summary>
         */
        public static bool SearchOnNode_Linear<NodeType, T>(NodeType node, IComparable<T> t, out int index)
            where NodeType : INode<NodeType, T>
        {
            int i;

            for (i = 0; i < node.EntryCount; i++)
            {
                int cmp = t.CompareTo(node.GetEntry(i));
                if (cmp < 0)
                {
                    break;
                }
                else if (cmp == 0)
                {
                    index = i;
                    return true;
                }
            }
            index = i;
            return false;
        }

        /*
         * <remarks>
         *  if not matched, index is set at the bigger entry (or one after the last entry)
         * </remarks>
         */
        public static bool SearchOnNode_Binary<NodeType, T>(NodeType node, IComparable<T> t, out int index)
            where NodeType : INode<NodeType, T>
        {
            int b, e;
            b = 0;
            e = node.EntryCount;
            for (; ; )
            {
                if (b == e)
                {
                    index = b;
                    return false;
                }
                index = (b + e) / 2;

                int cmp = t.CompareTo(node.GetEntry(index));
                if (cmp < 0)
                    e = index;
                else if (cmp > 0)
                    b = index + 1;
                else
                    return true;
            }
        }

        public delegate bool SearchOnNode<NodeType, T>(NodeType node, IComparable<T> t, out int index);

        /**
         * <summary>
         *  Search the node with specified value `t' from `node'
         *  The position to insert at is given by `target' and `index'
         *  
         *  a node is not allowed to have no entry
         *  
         * </summary>
         */
        public static bool Search<NodeType, T>(NodeType node, IComparable<T> t, out NodeType target,
            out int index, SearchOnNode<NodeType, T> searchOnNode)
            where NodeType : INode<NodeType, T>
        {
            if (node == null || node.EntryCount == 0)
            {
                target = node;
                index = 0;
                return false;
            }

            while (true)
            {
                if (searchOnNode(node, t, out index))
                {
                    target = node;
                    return true;
                }

                NodeType next = node.GetChild(index);
                if (next == null)
                {
                    target = node;
                    return false;
                }
                node = next;
            }
        }

        public static bool BinarySearch<NodeType, T>(NodeType node, IComparable<T> t, 
            out NodeType target, out int index)
            where NodeType : INode<NodeType, T>
        {
            return Search<NodeType, T>(node, t, out target, out index,
                new SearchOnNode<NodeType, T>(SearchOnNode_Binary<NodeType, T>));
        }

        /**
         * <summary>
         *  Search the node with specified value `t' from `node'
         *  The position to insert at is given by `target' and `index'
         *  
         *  a node is not allowed to have no entry
         *  
         *  TODO: test it
         *  
         * </summary>
         */
        public static void SearchToLeaf<NodeType, T>(NodeType node, IComparable<T> t, out NodeType target,
            out int index, SearchOnNode<NodeType, T> searchOnNode, bool left)
            where NodeType : INode<NodeType, T>
            where T : IComparable<T>
        {
            if (node == null || node.EntryCount == 0)
            {
                target = node;
                index = -1;
                return;
            }

            while (true)
            {
                if (searchOnNode(node, t, out index))
                {
                    if (!node.IsLeaf())
                    {
                        /**
                         * <remarks>
                         *  in-order neighbour of an entry on a non-leaf node 
                         *  must be at a leaf.
                         * </remarks>
                         */

                        if (left)
                        {
                            GotoPrevInorder<NodeType, T>(ref node, ref index);
                            index++;
                        }
                        else
                        {
                            GotoNextInorder<NodeType, T>(ref node, ref index);
                        }
                    }
                    target = node;
                    return;
                }

                NodeType next = node.GetChild(index);
                if (next == null)
                {
                    target = node;
                    return;
                }
                node = next;
            }
        }

        public static void BinarySearchToLeaf<NodeType, T>(NodeType node, IComparable<T> t, 
            out NodeType target, out int index, bool left)
            where NodeType : INode<NodeType, T>
            where T : IComparable<T>
        {
            SearchToLeaf<NodeType, T>(node, t, out target, out index,
                new SearchOnNode<NodeType, T>(SearchOnNode_Binary<NodeType, T>), left);
        }

        /**
         * <summary>
         *  Pre: p now has exactly `order' entries (accordingly, `order+1' children)
         *  Post: p has `order/2' entries, and ap has `order - 1 - order/2 = (order-1)/2' entries
         *        the key originally p's order/2-th is pushed up to the parent of p and ap,
         * </summary>
         */

        public static bool Split<NodeType, T>(ref NodeType p, int order, 
            INodeCreator<NodeType, T> creator)
            where NodeType : INode<NodeType, T>
            where T : IComparable<T>
        {
            NodeType ap = creator.Create();

            int knm = order / 2;
            int srcidx = knm + 1;   // spare the order/2-th item
            NodeType child;

            for ( ; srcidx < order; srcidx++)
            {
                child = p.GetChild(srcidx);
                ap.AppendChild(child);
                ap.AppendEntry(p.GetEntry(srcidx));
                if (child != null)
                {
                    child.Parent = ap;
                }
            }
            child = p.GetChild(srcidx);
            ap.AppendChild(child);
            if (child != null)
            {
                child.Parent = ap;
            }

            T x = p.GetEntry(knm);
            p.RemoveFrom(knm);

            NodeType q = p.Parent;
            if (q != null)
            {
                int i;
                SearchForChild_Binary<NodeType, T>(q, p, out i);

                q.InsertChild(i + 1, ap);
                q.InsertEntry(i, x);
                ap.Parent = q;
                p = q;

                return true;
            }
            else
            {   // p is the root
                // create a new root which takes the two pieces
                q = creator.Create();
                q.AppendChild(p);
                q.AppendChild(ap);
                q.AppendEntry(x);
                p.Parent = q;
                ap.Parent = q;
                p = q;

                return false;
            }
        }

        /**
         * <summary>
         *  Insert a new item at the specific position which is on a leaf
         * </summary>
         */
        public static void Insert<NodeType, T>(T t, NodeType at, int index, int order, 
            ref NodeType root, INodeCreator<NodeType, T> creator)
            where NodeType : INode<NodeType, T>
            where T : IComparable<T>
        {
            if (at != null)
            {
                at.InsertEntry(index, t);
                at.AppendChild(default(NodeType));
                while (true)
                {
                    if (at.EntryCount <= MaximalEntryCount(order))
                    {
                        break;
                    }
                    else if (!Split<NodeType, T>(ref at, order, creator))
                    {
                        root = at;
                        break;
                    }
                }
            }
            else
            {
                root = creator.Create();
                root.AppendEntry(t);
                root.AppendChild(default(NodeType));
                root.AppendChild(default(NodeType));
            }
        }

        public static void GetOneFromLeft<NodeType, T>(NodeType q, int iself)
            where NodeType : INode<NodeType, T>
        {
            int ileft = iself - 1;
            NodeType left = q.GetChild(ileft);

            T entryFromLeft = left.GetEntry(left.EntryCount - 1);
            NodeType nodeFromLeft = left.GetChild(left.ChildCount - 1);
            left.RemoveFrom(left.EntryCount - 1);

            T m = q.GetEntry(ileft);
            q.SetEntry(ileft, entryFromLeft);

            NodeType self = q.GetChild(iself);
            self.InsertEntry(0, m);
            self.InsertChild(0, nodeFromLeft);
            if (nodeFromLeft != null)
                nodeFromLeft.Parent = self;
        }

        public static void GetOneFromRight<NodeType, T>(NodeType q, int iself)
            where NodeType : INode<NodeType, T>
        {
            int iright = iself + 1;
            NodeType right = q.GetChild(iright);

            T entryFromRight = right.GetEntry(0);
            NodeType nodeFromRight = right.GetChild(0);
            right.RemoveChild(0);
            right.RemoveEntry(0);

            T m = q.GetEntry(iself);
            q.SetEntry(iself, entryFromRight);

            NodeType self = q.GetChild(iself);
            self.AppendEntry(m);
            self.AppendChild(nodeFromRight);
            if (nodeFromRight != null)
                nodeFromRight.Parent = self;
        }

        public static void Merge<NodeType, T>(ref NodeType q, int ientry, ref NodeType root)
            where NodeType : INode<NodeType, T>
        {
            NodeType left = q.GetChild(ientry);
            NodeType right = q.GetChild(ientry + 1);
            NodeType child;

            T m = q.GetEntry(ientry);

            left.AppendEntry(m);

            int i;
            for (i = 0; i < right.EntryCount; i++)
            {
                child = right.GetChild(i);
                left.AppendEntry(right.GetEntry(i));
                left.AppendChild(child);
                if (child != null)
                    child.Parent = left;
            }
            child = right.GetChild(i);
            left.AppendChild(child);
            if (child != null)
                child.Parent = left;

            // dispose right
            if (right is IDisposable)
                (right as IDisposable).Dispose();

            if ((object)q == (object)root && q.EntryCount == 1)
            {
                // dispose q
                if (q is IDisposable)
                    (q as IDisposable).Dispose();

                left.Parent = default(NodeType);
                q = root = left;
                return;
            }

            q.RemoveEntry(ientry);
            q.RemoveChild(ientry + 1);

            /**
             * q as a non-root node may be temporarily contains only one child
             * in the case of `order' = 4, however it is ok
             */ 
        }

        /**
         * <summary>
         *  `q' is a leaf (with only entries and no children)
         * </summary>
         */
        public static void RemoveFromLeaf<NodeType, T>(NodeType q, int index, int order, 
            ref NodeType root)
            where NodeType : INode<NodeType, T>
            where T : IComparable<T>
        {
            NodeType p = default(NodeType);

            if ((object)q == (object)root)
            {
                if (q.EntryCount == 1)
                {   // too small as a root
                    if (root is IDisposable)
                        (root as IDisposable).Dispose();
                    root = default(NodeType);
                }
                else
                {
                    q.RemoveEntry(index);
                    q.RemoveChild(q.ChildCount - 1);
                }
                return;
            }

            q.RemoveEntry(index);
            q.RemoveChild(q.ChildCount - 1);

            while (true)
            {
                if (q.ChildCount >= MinimalChildCount(order) )
                {   // not too small
                    break;
                }
                else
                {
                    p = q;
                    q = q.Parent;

                    if (q == null)
                        break;

                    int iself;
                    SearchForChild_Binary<NodeType, T>(q, p, out iself);

                    NodeType left = default(NodeType);
                    NodeType right = default(NodeType);

                    if (iself > 0)
                    {
                        left = q.GetChild(iself - 1);
                        if (left.ChildCount > MinimalChildCount(order))
                        {
                            GetOneFromLeft<NodeType, T>(q, iself);
                            break;
                        }
                    }

                    if (iself < q.ChildCount - 1)
                    {
                        right = q.GetChild(iself + 1);
                        if (right.ChildCount > MinimalChildCount(order))
                        {
                            GetOneFromRight<NodeType, T>(q, iself);
                            break;
                        }
                    }

                    if (left != null)
                    {   // merge with left sibling
                        Merge<NodeType, T>(ref q, iself - 1, ref root);
                    }
                    else    // right != null
                    {   // merge with right sibling
                        Merge<NodeType, T>(ref q, iself, ref root);
                    }
                }
            }
        }

        public static void Lift<NodeType, T>(ref NodeType q, ref int index)
            where NodeType : INode<NodeType, T>
        {
            NodeType p = q.GetChild(index + 1); // always lift from the right side

            while (true)
            {
                if (p.IsLeaf())
                {
                    q.SetEntry(index, p.GetEntry(0));
                    index = 0;
                    q = p;
                    break;
                }
                p = p.GetChild(0);
            }
        }

        public static void Remove<NodeType, T>(NodeType q, int index, int order,
            ref NodeType root)
            where NodeType : INode<NodeType, T>
            where T : IComparable<T>
        {
            if (!q.IsLeaf())
            {   // non-leaf
                Lift<NodeType, T>(ref q, ref index);
            }

            RemoveFromLeaf<NodeType, T>(q, index, order, ref root);
        }

        public static string ToString<NodeType, T>(NodeType q)
            where NodeType : INode<NodeType, T>
        {
            if (q == null)
                return "{ Empty Tree }";

            StringBuilder sb = new StringBuilder();

            sb.Append("Node( ");
            for (int i = 0; i < q.EntryCount; i++)
            {
                T t = q.GetEntry(i);
                sb.Append(t.ToString());
                if (i != q.EntryCount - 1)
                    sb.Append(", ");
            }
            sb.Append(" ) { ");

            NodeType n = default(NodeType);
            for (int i = 0; i < q.ChildCount; i++)
            {
                n = q.GetChild(i);
                if (n != null)
                {
                    string s = ToString<NodeType, T>(n);
                    sb.Append(s);
                }
                if (i != q.ChildCount - 1)
                    sb.Append(", ");
            }
            if (n == null) sb.Append("}");
            else sb.Append(" }");
            return sb.ToString();
        }

        public static void GotoFirstInorder<NodeType, T>(ref NodeType q, out int index)
            where NodeType : INode<NodeType, T>
        {
            while (true)
            {
                if (q.IsLeaf())
                {
                    index = 0;
                    return;
                }

                q = q.GetChild(0);
            }
        }

        public static void GotoLastInorder<NodeType, T>(ref NodeType q, out int index)
            where NodeType : INode<NodeType, T>
        {
            while (true)
            {
                if (q.IsLeaf())
                {
                    index = q.EntryCount - 1;
                    return;
                }

                q = q.GetChild(q.ChildCount - 1);
            }
        }

        public static bool GotoNextInorder<NodeType, T>(ref NodeType q, ref int index)
            where NodeType : INode<NodeType, T>
            where T : IComparable<T>
        {
            int iright = index + 1;

            if (q.IsLeaf())
            {
                if (iright < q.EntryCount)
                {
                    index = iright;
                    return true;
                }
                else
                {   /* the next key is on neigboring subtree */
                    while (true)
                    {
                        NodeType p = q.Parent;

                        if (p == null)
                        {
                            q = p;
                            index = -1;
                            return false;
                        }

                        int i;
                        SearchForChild_Binary<NodeType, T>(p, q, out i);

                        if (i < p.ChildCount - 1)
                        {
                            q = p;
                            index = i;
                            return true;
                        }

                        q = p;
                    }
                }
            }
            else
            {
                q = q.GetChild(iright); /* get to the node on the right */
                while (true)
                {
                    if (q.IsLeaf())
                    {
                        index = 0;
                        return true;
                    }
                    q = q.GetChild(0);
                }
            }
        }

        public static bool GotoPrevInorder<NodeType, T>(ref NodeType q, ref int index)
            where NodeType : INode<NodeType, T>
            where T : IComparable<T>
        {
            if (q.IsLeaf())
            {
                if (index > 0)
                {
                    index--;
                    return true;
                }
                else
                {   /* the next key is on neigboring subtree */
                    while (true)
                    {
                        NodeType p = q.Parent;

                        if (p == null)
                        {
                            q = p;
                            index = -1;
                            return false;
                        }

                        int i;
                        SearchForChild_Binary<NodeType, T>(p, q, out i);

                        if (i > 0)
                        {
                            q = p;
                            index = i - 1;
                            return true;
                        }

                        q = p;
                    }
                }
            }
            else
            {
                q = q.GetChild(index);  /* get to the node on the right */
                while (true)
                {
                    if (q.IsLeaf())
                    {
                        index = q.EntryCount - 1;
                        return true;
                    }
                    q = q.GetChild(q.ChildCount - 1);
                }
            }
        }

        public static bool CheckNode<NodeType, T>(NodeType q, int order, out int depth, out int count)
            where NodeType : INode<NodeType, T>
            where T : IComparable<T>
        {
            int entrynum = q.EntryCount;
            count = entrynum;
            depth = 1;

            if (entrynum > MaximalEntryCount(order))
                return false;
            else if (q.Parent != null && entrynum < MinimalEntryCount(order))
                return false;
            else if (entrynum == 0)
                return false;
            if (entrynum + 1 != q.ChildCount) 
                return false;

            depth = -1;
            for (int i = 0; i < q.ChildCount; i++)
            {
                int c = 0;
                int d = 0;
                NodeType p = q.GetChild(i);
                if (p != null)
                {
                    if ((object)q != (object)p.Parent)
                        return false;
                    if (!CheckNode<NodeType, T>(p, order, out d, out c))
                        return false;
                }
                if (depth == -1)
                    depth = d;
                else if (depth != d)
                    return false;   /* violates the condition that all leaves are at the same depth */
                count += c;
            }

            depth++;    /* to include the current level */

            return true;
        }

        public static bool CheckFromRoot<NodeType, T>(NodeType q, int order, out int count)
            where NodeType : INode<NodeType, T>
            where T : IComparable<T>
        {
            count = 0;
            if (q == null)
                return true;

            if (q.Parent != null)
                return false;

            int depth;
            if (!CheckNode<NodeType, T>(q, order, out depth, out count))
                return false;

            int index;
            GotoFirstInorder<NodeType, T>(ref q, out index);

            T prev = q.GetEntry(index);

            while (true)
            {
                if (!GotoNextInorder<NodeType, T>(ref q, ref index))
                    return true;

                T t = q.GetEntry(index);

                if (prev.CompareTo(t) >= 0)
                    return false;

                prev = t;
            }
        }
    }

    public class BTree<T>
        where T : IComparable<T>
    {
        public interface IHandle
        {
        }

        protected interface INode : BTree.INode<INode, T>, IHandle
        {
        }

        protected class Node : INode
        {
            public List<T> Entries = new List<T>();
            public List<Node> Children = new List<Node>();

            public Node()
            {
            }

            public INode GetChild(int index)
            {
                return Children[index];
            }

            public void SetChild(int index, INode node)
            {
                Children[index] = node as Node;
            }

            public void AppendChild(INode node)
            {
                Children.Add(node as Node);
            }

            public void InsertChild(int index, INode node)
            {
                Children.Insert(index, node as Node);
            }

            public void RemoveChild(int index)
            {
                Children.RemoveAt(index);
            }

            public T GetEntry(int index)
            {
                return Entries[index];
            }

            public void SetEntry(int index, T entry)
            {
                Entries[index] = entry;
            }

            public void AppendEntry(T entry)
            {
                Entries.Add(entry);
            }

            public void InsertEntry(int index, T entry)
            {
                Entries.Insert(index, entry);
            }

            public void RemoveEntry(int index)
            {
                Entries.RemoveAt(index);
            }

            public void RemoveFrom(int start)
            {
                int c = Entries.Count - start;
                Entries.RemoveRange(start, c);
                Children.RemoveRange(start + 1, c);
            }

            public bool IsLeaf()
            {
                return this.Children[0] == null;
            }

            public INode Parent { get; set; }

            public int EntryCount { get { return Entries.Count; } }
            public int ChildCount { get { return Children.Count; } }
        }

        protected class DisposableNode : Node, IDisposable
        {
            ~DisposableNode()
            {
                Dispose(false);
            }

            public void Dispose()
            {
                Dispose(true);
                GC.SuppressFinalize(this);
            }

            public virtual void Dispose(bool disposing)
            {
                if (mDisposed)
                    return;

                if (disposing)
                {
                    foreach (T t in this.Entries)
                    {
                        if (t is IDisposable)
                            (t as IDisposable).Dispose();
                        else
                            break;
                    }
                }

                mDisposed = true;
            }

            protected bool mDisposed = false;
        }

        protected class DisposableCreator : BTree.INodeCreator<INode, T>
        {
            public INode Create()
            {
                return new DisposableNode();
            }
        }

        protected class NondisposableCreator : BTree.INodeCreator<INode, T>
        {
            public INode Create()
            {
                return new NondisposableNode();
            }
        }

        protected class NondisposableNode : Node
        {
        }

        public BTree(int order)
        {
            Type ttype = typeof(T);
            if (ttype.GetInterface("IDisposable") == null)
                mCreator = new DisposableCreator();
            else
                mCreator = new NondisposableCreator();

            mOrder = order;
        }

        public bool Search(T t, out IHandle target, out int index)
        {
            INode node;
            bool b = BTree.Search<INode, T>(mRoot, t, out node, out index,
                new BTree.SearchOnNode<BTree<T>.INode, T>(BTree.SearchOnNode_Binary<INode, T>));
            target = node;
            return b;
        }

        public void Insert(T t, out IHandle target, out int index)
        {
            INode at;
            bool found = BTree.Search<INode, T>(mRoot, t, out at, out index, 
                new BTree.SearchOnNode<BTree<T>.INode,T>(BTree.SearchOnNode_Binary<INode, T>));
            if (found)
            {
                target = null;
                index = -1;
                return;
            }

            BTree.Insert<INode, T>(t, at, index, mOrder, ref mRoot, mCreator);
            target = at;
        }

        public void Remove(IHandle target, int index)
        {
            BTree.Remove<INode, T>(target as INode, index, mOrder, ref mRoot);
        }

        public override string ToString()
        {
            return BTree.ToString<INode, T>(mRoot);
        }

        public bool Check(out int count)
        {
            return BTree.CheckFromRoot<INode, T>(mRoot, mOrder, out count);
        }

        protected int mOrder = 0;
        protected INode mRoot = null;
        protected BTree.INodeCreator<INode, T> mCreator = null;
    }
}

